home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _iv_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  23.0 KB  |  893 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _iv_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. // -------------------------------------------------------------------
  17. //
  18. //  Interval Trees
  19. //
  20. //  Michael Seel   (1990/91)
  21. //
  22. // Implementation as described in
  23. // Kurt Mehlhorn: Data Structures and Algorithms 3, section VIII.5.1.1
  24. //
  25. // -------------------------------------------------------------------
  26.  
  27. #include <LEDA/impl/iv_tree.h>
  28.  
  29.  
  30. // -------------------------------------------------------------
  31. // member functions von iv_tree
  32. // -------------------------------------------------------------
  33.  
  34. // -------------------------------------------------------------
  35. // lrot() , rrot() , ldrot() , rdrot()
  36. // Rotationen am Knoten p
  37.  
  38. void iv_tree::lrot(iv_item p, iv_item q)
  39.  
  40. // p ist der zentrale Knoten um den rotiert wird
  41. // q ist der Vater von p
  42.  
  43. { 
  44.   iv_item h = p->son[_right];
  45.   p->son[_right] = h->son[_left];
  46.   h->son[_left] = p;
  47.    
  48.   if (!q) root=h;
  49.   else
  50.   {
  51.    if ( p == q->son[_left] )   q->son[_left]=h;
  52.    else q->son[_right]=h;
  53.   }; 
  54.   
  55.   p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  56.   h->gr=p->groesse()+h->son[_right]->groesse();
  57.  
  58.   reorganize_nodelist(h,p);
  59. }
  60.  
  61. void iv_tree::rrot(iv_item p, iv_item q)
  62.  
  63. // p ist der zentrale Knoten um den rotiert wird
  64. // q ist der Vater von p
  65.  
  66. { 
  67.   iv_item h = p->son[_left];
  68.   p->son[_left] = h->son[_right];
  69.   h->son[_right] = p;
  70.  
  71.   if (!q) root=h;
  72.   else
  73.   {
  74.    if ( p == q->son[_left] ) q->son[_left] = h;
  75.    else q->son[_right] = h; 
  76.   };
  77.  
  78.   p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  79.   h->gr=p->groesse()+h->son[_left]->groesse();
  80.  
  81.   reorganize_nodelist(h,p);
  82. }
  83.  
  84. void iv_tree::ldrot(iv_item p, iv_item q)
  85. { 
  86.   iv_item h = p->son[_right];
  87.   iv_item t = h->son[_left];
  88.   rrot(h,p);
  89.   lrot(p,q);
  90. }
  91.  
  92. void iv_tree::rdrot(iv_item p, iv_item q)
  93. {
  94.   iv_item h = p->son[_left];
  95.   iv_item t = h->son[_right];
  96.   lrot(h,p);
  97.   rrot(p,q);
  98. }
  99.  
  100. // ------------------------------------------------------------------
  101. // reorganize_nodelist()
  102. // reorganisiert die nach der Rotation falsch mit Intervallen belegten
  103. // Nodelists entsprechend neu.
  104.  
  105. void iv_tree::reorganize_nodelist(iv_item father, iv_item son)
  106. {
  107.   // nach Aendern des Dictionary-Typs in perfekte BB_trees mit Konstruk-
  108.   // tionsprozedur, die aus einer Liste von n geordneten Knoten ein neu-
  109.   // es Dictionary in Zeit O(n) erzeugt, werden von den folgenden 4 Ite-
  110.   // rationen je 2 in ein Misch_Sort Verfahren abgeaendert und die so
  111.   // auf father und son verteilten Intervalle in Linearzeit in die Kno-
  112.   // ten dictionarys eingebunden
  113.  
  114.   dic_item it;
  115.   nodelist_p fx = new nodelist;
  116.   nodelist_p fy = new nodelist;
  117.   nodelist_p sx = new nodelist;
  118.   nodelist_p sy = new nodelist;
  119.  
  120.   forall_items(it,*(father->x_nodelist())) // father->x_nodelist
  121.                             // liefert Pointer
  122.                             // auf x-Dictionary
  123.       {
  124.      if (split_in_x_interval(father , x_nodelist(father)->key(it)))
  125.         fx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
  126.          else
  127.         sx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
  128.       };
  129.   // die x-Knotenliste des Vaters wird durchsucht und alle passenden
  130.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  131.  
  132.   forall_items(it,*(son->x_nodelist())) // son->x_nodelist
  133.                              // liefert Pointer
  134.                             // auf x-Dictionary
  135.       {
  136.      if (split_in_x_interval(father , x_nodelist(son)->key(it))) 
  137.         fx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
  138.          else
  139.         sx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
  140.       };
  141.   // die x-Knotenliste des Sohns wird durchsucht und alle passenden
  142.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  143.  
  144.  
  145.   forall_items(it,*(father->y_nodelist())) // father->y_nodelist
  146.                                    // liefert Pointer
  147.                                // auf y-Dictionary
  148.       {
  149.      if (split_in_y_interval(father , y_nodelist(father)->key(it)))
  150.         fy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
  151.          else
  152.         sy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
  153.       };
  154.   // die y-Knotenliste des Vaters wird durchsucht und alle passenden
  155.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  156.  
  157.   forall_items(it,*(son->y_nodelist())) // son->y_nodelist
  158.                         // liefert Pointer
  159.                         // auf y-Dictionary
  160.       {
  161.      if (split_in_y_interval(father, y_nodelist(son)->key(it)))
  162.         fy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
  163.          else
  164.         sy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
  165.       };
  166.   // die y-Knotenliste des Sohns wird durchsucht und alle passenden
  167.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  168.  
  169.   delete x_nodelist(father);
  170.   delete y_nodelist(father);
  171.   delete x_nodelist(son);
  172.   delete y_nodelist(son);
  173.   // alte Dictionaries werden geloescht und freigegeben
  174.   father->x_nl = fx;
  175.   father->y_nl = fy;
  176.   son->x_nl = sx;
  177.   son->y_nl = sy;
  178.   // Knotenlisten werden mit neu angeordneten Dictionaries intialisiert
  179. }
  180.  
  181.  
  182. // ------------------------------------------------------------
  183. // search()
  184. // nachher: st = ( pk ,..., p1 ) mit 
  185. //          pk = locate(y) , p1 = root 
  186. //          p1 , ... , pk ist Suchpfad nach y
  187. // liefert inneren Knoten k mit key(k) = y , falls existiert
  188. //         0                               , sonst
  189.  
  190. iv_item iv_tree::search(split_item x)
  191.  
  192. { 
  193.   st.clear();
  194.   iv_item p = root;
  195.   iv_item searched = 0;
  196.  
  197.   if (!root) return 0;         // Baum leer
  198.   while (!p->blatt())
  199.   { 
  200.     if (cmp(x,split_value(p))<=0)
  201.     {
  202.       if (cmp(x,split_value(p))==0) searched = p;
  203.       st.push(p);
  204.       p = p->son[_left];
  205.     }
  206.     else
  207.     {
  208.       st.push(p);
  209.       p = p->son[_right];
  210.     }
  211.   }
  212.   st.push(p);
  213.   return searched;
  214. }
  215.  
  216.  
  217. // ------------------------------------------------------------------
  218. // iv_insert(x_typ,x_typ)
  219. // fuegt ein neues Intervall (x,y) in den Baum ein
  220. // gibt Zeiger auf Knoten, in dessen Knotenliste Intervall
  221. // eingefuegt wurde, zurueck.
  222.  
  223. iv_item iv_tree::iv_insert(x_typ x, x_typ y)
  224. {
  225.  if (y<x)
  226.  {
  227.   error_handler(0,"kein Intervall zum einfuegen");
  228.   return 0;
  229.  }
  230.  else
  231.  {
  232.   interval_item x_iv = new interval(x,y);
  233.   interval_item y_iv = new interval(y,x);
  234.   return ins(x_iv,y_iv,++interval_nb);
  235.  }
  236. }
  237.  
  238. // ------------------------------------------------------------------
  239. // ins(interval_item,interval_item,int)
  240. // fuegt den entsprechenden Knoten in die Grundstruktur mit dem 
  241. // entsprechenden split_value und fuegt die beiden Intervalle am
  242. // entsprechenden Knoten in die Knotenlisten
  243.  
  244. iv_item iv_tree::ins(interval_item x, interval_item y, int lfnr) 
  245. {
  246.  iv_item p;
  247.  iv_item t;
  248.  iv_item father;
  249.  split_pair x_pair(x->koo1,-lfnr);
  250.  split_item x_split = &x_pair; 
  251.  
  252.  if (!root)                                     // neuer Baum
  253.  { 
  254.   root = new iv_node(x_split);
  255.   anzahl=1;
  256.  }
  257.  else     // Baum existiert schon !!
  258.   if (root->blatt())
  259.   {
  260.     if (cmp(x_split,split_value(root))<0)
  261.     {
  262.      iv_item help = new iv_node(x_split);
  263.      root = new iv_node(x_split,node,help,root);
  264.      if (x_split->key1==split_value(root->son[_right])->key1)
  265.       nodelist_swap(root , root->son[_right]);
  266.      anzahl++;
  267.     }
  268.     else
  269.      if (cmp(x_split,split_value(root))>0)
  270.      {
  271.       iv_item help = new iv_node(x_split);
  272.       root = new iv_node(split_value(root),node,root,help);
  273.       nodelist_swap(root , root->son[_left]);
  274.       anzahl++;
  275.      }
  276.   }
  277.   else // in Knoten von nicht trivialem Baum wird eingefuegt
  278.   {
  279.     search(x_split);
  280.     p = st.pop();
  281.     father = st.top();
  282.   
  283.     if(cmp(x_split,split_value(p))<0)
  284.     {
  285.      iv_item help = new iv_node(x_split);
  286.      p = new iv_node(x_split,node,help,p);
  287.      // neuer Knoten in p mit split x, x-Blatt links, p-Blatt rechts
  288.      if (x_split->key1==split_value(p->son[_right])->key1)
  289.       nodelist_swap(p , p->son[_right]);
  290.  
  291.      if (cmp(split_value(p),split_value(father))<=0)
  292.        father->son[_left] = p;
  293.      else
  294.        father->son[_right] = p;
  295.      anzahl++;
  296.     }
  297.     else
  298.      if (cmp(x_split,split_value(p))>0)
  299.      {           
  300.       iv_item help = new iv_node(x_split);
  301.       p = new iv_node(split_value(p),node,p,help);
  302.       // neuer Knoten in p mit split p, p-Blatt links, x-Blatt rechts
  303.       nodelist_swap(p , p->son[_left]);
  304.  
  305.       if (cmp(split_value(p),split_value(father))<=0)
  306.         father->son[_left] = p;
  307.       else
  308.         father->son[_right] = p;
  309.       anzahl++;
  310.      }
  311.   }
  312.  
  313.   while (!st.empty())                          // rebalancieren
  314.   { 
  315.     t=st.pop();
  316.     father = st.empty() ? 0 : st.top();
  317.     t->gr++;  
  318.     float i = t->bal();
  319.     if (i < alpha)
  320.     {
  321.      if (t->son[_right]->bal()<=d)
  322.        lrot(t,father);
  323.      else
  324.        ldrot(t,father);
  325.     }
  326.     else
  327.     if (i>1-alpha) 
  328.     {
  329.       if (t->son[_left]->bal()>d)
  330.     rrot(t,father);
  331.       else
  332.     rdrot(t,father);
  333.     }
  334.   }
  335.   
  336.   p = sink(root,x,y,lfnr);
  337.   return p;    
  338. }
  339.  
  340.  
  341. // ------------------------------------------------------------------
  342. // sink()
  343. // laesst Intervall im Baum bis zu dem Knoten v abwaerts gleiten an dem 
  344. // gilt: 1.Komponente von split_value(v) <in> Intervall <Teilmenge von> x_range(v)
  345.  
  346. iv_item iv_tree::sink(iv_item v, interval_item x, interval_item y, int lfnr)
  347. {
  348.    if (v)
  349.    {
  350.      if (split_in_x_interval(v,x))
  351.      {
  352.        if (x_nodelist(v)->lookup(x))
  353.        {
  354.          error_handler(0,"Interval wurde schon eingefuegt!\n");
  355.      split_pair h(x->koo1,-lfnr);
  356.      split_item hi=&h;
  357.      del(hi);
  358.      return 0;
  359.        }
  360.        x_nodelist(v)->insert(x,lfnr);
  361.        y_nodelist(v)->insert(y,lfnr);
  362.        return v;
  363.      }
  364.      else
  365.      {
  366.        if (x->cmp(x->koo2,split_value(v)->key1) < 0)
  367.        { 
  368.      return sink(v->son[_left],x,y,lfnr);
  369.        }
  370.        else
  371.        if (x->cmp(split_value(v)->key1,x->koo1) < 0)
  372.        {
  373.      return sink(v->son[_right],x,y,lfnr);
  374.        }
  375.      }
  376.    }
  377.  
  378.    return 0;
  379. }
  380.  
  381. // ------------------------------------------------------------------
  382. // iv_delete(x_typ,x_typ)
  383. // loescht ein Intervall (x,y) aus dem Baum
  384. // gibt Zeiger auf geloeschtes intervall zurueck 
  385.  
  386. void iv_tree::iv_delete(x_typ x, x_typ y)
  387. {
  388.   if (y<x) 
  389.   {
  390.    error_handler(0,"kein Intervall!\n");
  391.    return;
  392.   }
  393.   else
  394.   if (!root) error_handler(0,"Baum ist leer!\n");
  395.   else
  396.   {
  397.    iv_item v = root;
  398.    interval xi(x,y);
  399.    interval yi(y,x);
  400.    interval_item x_iv = ξ
  401.    interval_item y_iv = &yi; 
  402.    while ( !split_in_x_interval(v,x_iv) && !v->blatt() )
  403.    {
  404.     if (split_value(v)->cmp(y,split_value(v)->key1) < 0)
  405.     {
  406.       v = v->son[_left];
  407.     }
  408.     if (split_value(v)->cmp(split_value(v)->key1,x) < 0) 
  409.     {
  410.       v = v->son[_right];
  411.     }
  412.    }
  413.    // nun ist v der Knoten an dem das Intervall [x,y] abgespeichert sein muesste
  414.    dic_item help1 = x_nodelist(v)->lookup(x_iv);
  415.    dic_item help2 = y_nodelist(v)->lookup(y_iv);
  416.    if (!(help1 && help2))
  417.    {
  418.     error_handler(0,"Intervall nicht vorhanden!\n");
  419.     return;
  420.    }
  421.    else
  422.    {
  423.     split_pair s(x_nodelist(v)->key(help1)->koo1,-x_nodelist(v)->inf(help1));
  424.     split_item search_split = &s; 
  425.     x_nodelist(v)->del_item(help1);
  426.     y_nodelist(v)->del_item(help2);
  427.     if (!del(search_split)) 
  428.       error_handler(1,"Intervall geloescht, Grundstruktur nicht in Ordnung\n");
  429.    } 
  430.   }
  431. }
  432.  
  433.  
  434. // ------------------------------------------------------------------
  435. // del()
  436. // loescht Item it im Baum mit split(it)=y , falls existiert
  437. // gibt 1 zurueck, falls existent und geloescht
  438. // gibt 0 zurueck, falls nicht existent
  439.  
  440. int iv_tree::del(split_item y)
  441. {
  442.   st.clear();
  443.   if (root==0) return 0;                         // s.n.
  444.  
  445.   if (root->blatt())                             // Wurzel loeschen
  446.     if (cmp(y,split_value(root))==0)
  447.     { 
  448.       if (!x_nodelist(root)->empty()) 
  449.      error_handler(1,"noch Intervalle in zu loeschender Wurzel!\n");
  450.       anzahl=0; 
  451.       delete root;
  452.       root=0; 
  453.       return 1; 
  454.     }
  455.     else
  456.     {
  457.      error_handler(0,"Element nicht im Baum\n");  
  458.      return 0;
  459.     }
  460.   else // Baum nicht trivial
  461.   {
  462.     iv_item p,father;
  463.     iv_item pp=search(y);
  464.     if (st.size()==2)                            // Sohn der Wurzel
  465.     { 
  466.       p=st.pop();
  467.       father=st.pop();
  468.  
  469.       int v1 = cmp(y,split_value(father));
  470.       if (cmp(y,split_value(p))!=0)
  471.       {
  472.         return 0;
  473.       }
  474.       anzahl--;
  475.       if (v1<=0)
  476.       {
  477.         root=root->son[_right];
  478.     if(!x_nodelist(father)->empty())
  479.       nodelist_swap(father,root);
  480.       }
  481.       else
  482.       {
  483.         root=root->son[_left];
  484.     if(!x_nodelist(father)->empty())
  485.       {
  486.         if (!root->son[_right]) 
  487.            nodelist_swap(father,root);
  488.             else
  489.         if ((root->son[_right])&&(x_nodelist(father)->size()==2))
  490.             {
  491.            nodelist_swap(father,root->son[_right]);
  492.            reorganize_nodelist(root,root->son[_right]);
  493.             }
  494.             else
  495.            nodelist_swap(father,root->son[_right]);
  496.           } 
  497.       }
  498.       if (!x_nodelist(father)->empty() || !x_nodelist(p)->empty())
  499.     error_handler(1,"Knotenlisten beim Loeschen nicht leer\n");
  500.       delete father;
  501.       delete p;
  502.     }
  503.     else                                // Blatt mit Tiefe >= 2     
  504.     {
  505.       iv_item p=st.pop();
  506.       if (cmp(y,split_value(p))!=0)
  507.       { 
  508.     return 0;
  509.       }
  510.       iv_item q = st.pop();
  511.       father = st.top();
  512.       int v1 = cmp(y,split_value(father));
  513.       int v2 = cmp(y,split_value(q));
  514.       anzahl--;
  515.       if (v1<=0)
  516.         if (v2<=0)
  517.     {
  518.       father->son[_left]=q->son[_right];
  519.       if(!x_nodelist(q)->empty())
  520.         nodelist_swap(q,father->son[_right]);
  521.         }
  522.         else
  523.     {
  524.       father->son[_left]=q->son[_left];
  525.       if(!x_nodelist(q)->empty())
  526.       {
  527.         if (!father->son[_left]->son[_right])
  528.            nodelist_swap(q,father->son[_left]);
  529.             else
  530.         if ((father->son[_left]->son[_right])&&(x_nodelist(q)->size()==2))
  531.             {
  532.            nodelist_swap(q,father->son[_left]->son[_right]);
  533.            reorganize_nodelist(father->son[_left],father->son[_left]->son[_right]);
  534.             }
  535.             else
  536.            nodelist_swap(q,father->son[_left]->son[_right]);
  537.           } 
  538.         }
  539.       else
  540.     if (v2<=0)
  541.     {
  542.       father->son[_right]=q->son[_right];
  543.       if(!x_nodelist(q)->empty())
  544.         nodelist_swap(q,father->son[_right]);
  545.         }
  546.         else
  547.     {
  548.       father->son[_right]=q->son[_left];
  549.       if(!x_nodelist(q)->empty())
  550.       {
  551.         if (!father->son[_right]->son[_right])
  552.            nodelist_swap(q,father->son[_right]);
  553.             else
  554.         if ((father->son[_right]->son[_right])&&(x_nodelist(q)->size()==2))
  555.             {
  556.            nodelist_swap(q,father->son[_right]->son[_right]);
  557.            reorganize_nodelist(father->son[_right],father->son[_right]->son[_right]);
  558.             }
  559.             else
  560.            nodelist_swap(q,father->son[_right]->son[_right]);
  561.           } 
  562.         }
  563.       if (!x_nodelist(p)->empty())
  564.     error_handler(1,"Knotenlisten von p beim Loeschen nicht leer");
  565.       delete p;
  566.       delete q;
  567.     }
  568.   }
  569.   
  570.   // REBALANCIEREN
  571.   iv_item p;
  572.   iv_item father;
  573.   while (!st.empty())
  574.   { p = st.pop();
  575.     father = st.empty() ? 0 : st.top() ;
  576.     p->gr--;              
  577.     float i=p->bal();
  578.     if (i<alpha)
  579.       if (p->son[_right]->bal() <= d)
  580.        lrot(p,father);
  581.       else
  582.        ldrot(p,father);
  583.     else
  584.     if (i>1-alpha)
  585.       if(p->son[_left]->bal() > d)
  586.        rrot(p,father);
  587.       else
  588.        rdrot(p,father);
  589.   }
  590.   return 1;
  591. }
  592.  
  593.  
  594. // ------------------------------------------------------------------
  595. // iv_query(x_typ,x_typ)
  596. // gibt alle Intervalle in einer Liste zurueck, die das mit 
  597. // den Parametern uebergebene Intervall schneiden.
  598.  
  599. interval_list iv_tree::iv_query(x_typ x, x_typ y)
  600. {
  601.  interval_list query_list;
  602.  if (!root)
  603.  {
  604.    error_handler(0,"Baum ist leer");
  605.    return query_list;
  606.  } 
  607.  if (y<x)
  608.  { 
  609.   error_handler(0,"kein Intervall\n");
  610.   return query_list;
  611.  }
  612.  split_pair xp(x,-MAXINT);
  613.  split_pair yp(y,MAXINT);
  614.  split_item xi = &xp;
  615.  split_item yi = &yp;
  616.  iv_item v = root;
  617.  int done=0;
  618.  // Bestimmung der P-Menge mit Hilfe von search-Schleife nach x,
  619.  // unterwegs Abzweig zu search nach y
  620.  // alle zwischen den Pfaden liegenden Knoten werden mit get_all
  621.  // abgearbeitet
  622.  // jeder Knoten wird mit Hilfe von check_iv() nach den in den 
  623.  // Knotenmengen vorhandenen Intervallen, die die Schnittbegingung
  624.  // erfuellen abgearbeitet.
  625.  while (!v->blatt())
  626.  {
  627.    check_nodelist(query_list,v,x,y);
  628.    if (cmp(xi,split_value(v))<=0) // xi <= split(v)
  629.    {
  630.      if ((cmp(yi,split_value(v))>0) && !done)
  631.      {
  632.        y_search(query_list,v->son[_right],yi,x,y);
  633.        done=1;
  634.      }
  635.      else
  636.      {
  637.        if (done)  // klappert den gesamten Unterbaum von v der C-Menge ab
  638.          get_all_in_tree(query_list,v->son[_right]);
  639.      }
  640.      v=v->son[_left];
  641.    }
  642.    else  // xi > split(v)
  643.    {
  644.      v=v->son[_right];
  645.    }
  646.  }
  647.  check_nodelist(query_list,v,x,y);
  648.  return query_list;
  649. }
  650.  
  651. // ------------------------------------------------------------------
  652. // y_search()
  653. // verzweigt vom Knoten v aus, in einen neuen Suchpfad nach dem y-
  654. // Wert des query-Intervalls und fuehrt auch dort die P-checks durch
  655.  
  656. void iv_tree::y_search(interval_list& il, iv_item v, split_item ys,
  657.                x_typ x, x_typ y)
  658. {
  659.  while (!v->blatt())
  660.  {
  661.    check_nodelist(il,v,x,y);
  662.    if (cmp(ys,split_value(v))<=0) // ys <= split(v)
  663.      v=v->son[_left];
  664.    else  // ys > split(v)
  665.    {
  666.      get_all_in_tree(il,v->son[_left]);
  667.      // klappert den gesamten Unterbaum von v der C-Menge ab
  668.      v=v->son[_right];
  669.    }
  670.  }
  671.  check_nodelist(il,v,x,y);
  672. }
  673.   
  674. // ------------------------------------------------------------------
  675. // check_nodelist()
  676. // ueberprueft entsprechend der in MEHLHORN III dargestellten Fall-
  677. // unterscheidung fuer P-Knoten die jeweilige x- oder y-Knotenliste
  678. // oder uebernimmt alle Eintraege.
  679.  
  680. void iv_tree::check_nodelist(interval_list& il, iv_item v, x_typ x, x_typ y)
  681. {
  682.   if ((split_value(v)->cmp(x,split_value(v)->key1)<=0)
  683.   && (split_value(v)->cmp(split_value(v)->key1,y)<=0))
  684.   // dann ist split(v) im query-Intervall, das damit alle Intervalle
  685.   // der Knotenliste schneidet.
  686.     take_all_iv(il,v);
  687.   else
  688.   if (split_value(v)->cmp(x,split_value(v)->key1)>0)
  689.   // Intervall oberhalb des split(v)
  690.     check_y_iv(il,v,x);
  691.   else
  692.   // Intervall unterhalb des split(v)
  693.     check_x_iv(il,v,y);
  694. }
  695.  
  696.  
  697. // ------------------------------------------------------------------
  698. // get_all_in_tree()
  699. // uebernimmt alle im Unterbaum des Knotens v abgespeicherten Inter-
  700. // valle in die uebergebene Liste
  701. // entspricht einer Teilmenge der C-Menge
  702.  
  703. void iv_tree::get_all_in_tree(interval_list& il, iv_item v)
  704. {
  705.   take_all_iv(il,v);
  706.   if (!v->blatt())
  707.   { 
  708.     get_all_in_tree(il,v->son[_left]);
  709.     get_all_in_tree(il,v->son[_right]);
  710.   }
  711. }
  712.  
  713. // ------------------------------------------------------------------
  714. // take_all_iv()
  715. // uebernimmt an einem Knoten alle abgespeicherten Intervalle
  716. // in die mituebergebene Liste.
  717.  
  718. void iv_tree::take_all_iv(interval_list& il, iv_item v)
  719. {
  720.   dic_item it;
  721.   forall_items(it,*(v->x_nodelist()))
  722.   {
  723.     interval_item help = x_nodelist(v)->key(it);
  724.     interval_item ii = new interval(help->koo1, help->koo2);
  725.     il.append(ii);
  726.   }
  727. }
  728.  
  729.  
  730. // ------------------------------------------------------------------
  731. // check_y_iv()
  732. // ueberprueft an einem Knoten alle Intervalle der y-Knotenliste
  733. // auf Schnittbedingung mit dem uebergebenen x-Wert des query-
  734. // Intervalls und haengt bei erfuellter Schnittbedingung das In-
  735. // tervall an die mituebergebene Liste an.
  736.  
  737.   void iv_tree::check_y_iv(interval_list& il, iv_item v, x_typ x)
  738.   { 
  739.       if (!y_nodelist(v)->empty())
  740.       {
  741.     dic_item maxit = y_nodelist(v)->max();
  742.     if (split_value(v)->cmp(y_nodelist(v)->key(maxit)->koo1,x)>=0) 
  743.     {
  744.       dic_item it = maxit;
  745.       int intersect = 1;
  746.       while(it && intersect) 
  747.       {
  748.         if (split_value(v)->cmp(y_nodelist(v)->key(it)->koo1,x)>=0) 
  749.         {
  750.          interval_item help = y_nodelist(v)->key(it); 
  751.          interval_item ii = new interval(help->koo2, help->koo1);
  752.          // die Intervalle der y-Knotenliste haben 1. Komponente
  753.          // y und 2. Komponente x, zur Rueckgabe ist aber die
  754.          // umgekehrte Reihenfolge verlangt.
  755.          il.append(ii);
  756.         }
  757.         else
  758.          intersect = 0;
  759.         it = y_nodelist(v)->pred(it);
  760.           }
  761.         }
  762.       }
  763.   }
  764.  
  765. // ------------------------------------------------------------------
  766. // check_x_iv()
  767. // ueberprueft an einem Knoten alle Intervalle der x-Knotenliste
  768. // auf Schnittbedingung mit dem uebergebenen y-Wert des query-
  769. // Intervalls und haengt bei erfuellter Schnittbedingung das In-
  770. // tervall an die mituebergebene Liste an.
  771.  
  772.   void iv_tree::check_x_iv(interval_list& il, iv_item v, x_typ y)
  773.   { 
  774.       if (!x_nodelist(v)->empty())
  775.       {
  776.     dic_item minit = x_nodelist(v)->min();
  777.     if (split_value(v)->cmp(x_nodelist(v)->key(minit)->koo1,y)<=0) 
  778.     {
  779.       dic_item it = minit; 
  780.       int intersect = 1;
  781.       while(it && intersect) 
  782.       {
  783.         if (split_value(v)->cmp(x_nodelist(v)->key(it)->koo1,y)<=0) 
  784.         {
  785.          interval_item help = x_nodelist(v)->key(it); 
  786.          interval_item ii = new interval(help->koo1, help->koo2);
  787.          // die Intervalle der x-Knotenliste haben 1. Komponente
  788.          // x und 2. Komponente y.
  789.          il.append(ii);
  790.         }
  791.         else
  792.          intersect = 0;
  793.         it = x_nodelist(v)->succ(it);
  794.           }
  795.         }
  796.       }
  797.   }
  798.  
  799.  
  800. //-----------------------------------------------------------------------
  801. // void print_split(iv_item) 
  802. // gibt split_value von p aus
  803.  
  804.   void iv_tree::print_split(iv_item it)   
  805.   { 
  806.     if (it)
  807.       { it->split_value()->print();
  808.         if (it->blatt()) text(" (blatt)\n");
  809.         else text("(Knoten)\n");
  810.        }
  811.     else
  812.       cout << " Knoten leer!\n";
  813.   }
  814.  
  815.  
  816.  
  817.  
  818. //-----------------------------------------------------------------------
  819. // void pr_iv_tree(iv_item p;int blancs)
  820. // gibt den Baum mit Wurzel p aus
  821.  
  822. void iv_tree::pr_iv_tree(iv_item p,int blancs)
  823. {
  824.  if (p==0)
  825.  {
  826.   for (int j=1;j<=blancs;j++) cout << " ";
  827.   cout << "NIL\n";
  828.   return;
  829.  }
  830.  else
  831.  {
  832.   pr_iv_tree(p->son[_left],blancs+10); 
  833.   for (int j=1;j<=blancs;j++) cout << " ";
  834.   
  835.   cout << "(" << p->split_value()->key1 << "," << p->split_value()->key2;
  836.   cout << ") ";
  837.   pr_iv_list(p);
  838.   pr_iv_tree(p->son[_right],blancs+10); 
  839.  }
  840. }
  841.  
  842. //-----------------------------------------------------------------------
  843. // void pr_iv_list(iv_item p)
  844. // gibt die Intervalliste eines Knotens p aus
  845.  
  846. void iv_tree::pr_iv_list(iv_item p)
  847. {
  848.   dic_item it;
  849.   forall_items(it,*(p->x_nodelist()))
  850.   { cout << "[" << x_nodelist(p)->key(it)->koo1;
  851.     cout << "," << x_nodelist(p)->key(it)->koo2 << "]"; 
  852.     cout << "#" << x_nodelist(p)->inf(it) << ";";
  853.    }
  854.   cout << "  *  ";
  855.   forall_items(it,*(p->y_nodelist()))
  856.   { cout << "[" << y_nodelist(p)->key(it)->koo1;
  857.     cout << "," << y_nodelist(p)->key(it)->koo2<< "]"; 
  858.     cout << "#" << y_nodelist(p)->inf(it) << ";";
  859.    }
  860.   cout << "\n";
  861. }
  862.  
  863. //-----------------------------------------------------------------------
  864. // void pr_list()
  865. // gibt die zurueckgegebene Intervalliste der query aus
  866.  
  867. void iv_tree::pr_list(interval_list& il)
  868. {
  869.   cout << "Liste: \n";
  870.   if(il.empty()) cout << " leer\n";
  871.   list_item it;
  872.   forall_list_items(it,il)
  873.     il.contents(it)->print(); 
  874. }
  875.     
  876.  
  877. //-----------------------------------------------------------------------
  878. // Funktion fuer Destruktor
  879. //-----------------------------------------------------------------------
  880.   
  881. void iv_tree::deltree(iv_item p)
  882. {
  883.  if (p)
  884.  {
  885.   if (!p->blatt())
  886.   {
  887.    deltree(p->son[_left]);
  888.    deltree(p->son[_right]);
  889.   }
  890.   delete(p);
  891.  }
  892. }
  893.